package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         152,
		Discription: "乘积最大子数组",
		Level:       2,
		Labels: map[string]int{
			"动态规划":  1,
			"有限状态机": 1,
		},
	})
}

func MaxProduct(nums []int) int {
	res := nums[0]
	n := len(nums)
	preMax := nums[0]
	preMin := nums[0]

	for i := 1; i < n; i++ {
		if nums[i] == 0 {
			preMax = 0
			preMin = 0
		} else if nums[i] > 0 {
			preMax = max(nums[i], preMax*nums[i])
			preMin = min(nums[i], preMin*nums[i])
		} else {
			//这里要先暂存下上一个位置的max，后边min的转换要用到
			tempMax := preMax
			preMax = max(nums[i], preMin*nums[i])
			preMin = min(nums[i], tempMax*nums[i])
		}

		res = max(res, preMax)
	}

	return res
}
